/*************************************************************************
 * File Name:    Word_Ladder.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 27 Oct 2013 02:20:37 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Word ladderLength
 | Given two words (start and end), and a dictionary, find the length of
 | shortest transformation sequence from start to end, such that:
 |
 | Only one letter can be changed at a time
 | Each intermediate word must exist in the dictionary
 | For example,
 |
 | Given:
 | start = "hit"
 | end = "cog"
 | dict = ["hot","dot","dog","lot","log"]
 |
 | As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
 |
 | return its length 5.
 |
 | Note:
 |  Return 0 if there is no such transformation sequence.
 |  All words have the same length.
 |  All words contain only lowercase alphabetic characters.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        map<string, vector<string> > transform;
        
        for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
            string t(*it);
            
            for (size_t i = 0; i < t.size(); ++i) {
                char ch = t[i];
                for (int ic = 'a'; ic <= 'z'; ++ic) {
                    if (ic == ch) continue;
                    t[i] = ic;
                    if (dict.find(t) != dict.end()) {
                        transform[*it].push_back(t);
                    }
                }
                t[i] = ch;
            }
        }
        int ans = 0;
        queue<pair<string, int> > Q;
        Q.push(make_pair(start, 1));
        pair<string, int> t;
        
        while (!Q.empty()) {
            t = Q.front(), Q.pop();
            if (t.first == end) {
                ans = t.second;
                break;
            }
            vector<string> &ttrans = transform[t.first];
            for (size_t i = 0; i < ttrans.size(); ++i) {
                if (transform.find(ttrans[i]) == transform.end()) continue;
                Q.push(make_pair(ttrans[i], t.second + 1));
            }
            transform.erase(t.first);
        }
        return ans;
    }

    int ladderLength_tle_2(string start, string end, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        
        vector<string> words;
        
        words.push_back(start);
        for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
            if (*it == start || *it == end) continue;
            words.push_back(*it);
        }
        words.push_back(end);
        
        vector<vector<int> > transform(words.size());

        for (size_t i = 0; i < words.size(); ++i) {
            for (size_t j = i + 1; j < words.size(); ++j) {
                if (words[i].size() != words[j].size()) continue;
                int cnt = 0;
                for (size_t k = 0; k < words[i].size(); ++k) {
                    if (words[i][k] != words[j][k]) ++cnt;
                    if (cnt > 1) break;
                }
                if (cnt == 1) {
                    transform[i].push_back(j);
                    transform[j].push_back(i);
                }
            }
        }
        
        queue<int> startQ, endQ;
        vector<pair<bool, int> > start_visited(words.size(), make_pair(false, 0));
        vector<pair<bool, int> > end_visited(words.size(), make_pair(false, 0));
        startQ.push(0);
        endQ.push(words.size() - 1);
        
        start_visited[0].first = true;
        start_visited[0].second = 1;
        
        end_visited[words.size() - 1].first = true;
        end_visited[words.size() - 1].second = 1;
        
        int ans = 0;
        int id;
        while (!startQ.empty() && !endQ.empty()) {
            id = startQ.front(), startQ.pop();
            for (size_t i = 0; i < transform[id].size(); ++i) {
                if (start_visited[transform[id][i]].first) continue;
                if (end_visited[transform[id][i]].first) {
                    ans = start_visited[id].second + end_visited[transform[id][i]].second;
                }
                startQ.push(transform[id][i]);
                start_visited[transform[id][i]].first = true;
                start_visited[transform[id][i]].second = start_visited[id].second + 1;
            }
            if (ans != 0) break;
            
            id = endQ.front(), endQ.pop();
            for (size_t i = 0; i < transform[id].size(); ++i) {
                if (end_visited[transform[id][i]].first) continue;
                if (start_visited[transform[id][i]].first) {
                    ans = start_visited[transform[id][i]].second + end_visited[id].second;
                }
                endQ.push(transform[id][i]);
                end_visited[transform[id][i]].first = true;
                end_visited[transform[id][i]].second = end_visited[id].second + 1;
            }
            if (ans != 0) break;
        }
        return ans;
    }

    int ladderLength_tle(string start, string end, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        
        map<string, vector<string> > transform;
        for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
            for (dict_iter_t iter = dict.begin(); iter != dict.end(); ++iter) {
                if (it == iter || it->size() != iter->size()) continue;
                int cnt = 0;
                for (size_t i = 0; i < it->size(); ++i) {
                    if (it->at(i) != iter->at(i)) ++cnt;
                    if (cnt > 1) break;
                }
                if (cnt == 1) {
                    transform[*it].push_back(*iter);
                }
            }
        }
        int ans = 0;
        set<string> used;
        pair<string, int> t;
        queue<pair<string, int> > Q;
        Q.push(make_pair(start, 1));
        while (!Q.empty()) {
            t = Q.front(), Q.pop();
            if (t.first == end) {
                ans = t.second;
                break;
            }
            vector<string> &transf = transform[t.first];
            
            for (size_t i = 0; i < transf.size(); ++i) {
                if (used.find(transf[i]) != used.end()) {
                    if (transf[i] == end) {
                        ans = t.second + 1;
                        break;
                    }
                    
                    Q.push(make_pair(transf[i], t.second + 1));
                    used.insert(transf[i]);
                }
            }
            if (ans != 0) break;
        }
        return ans;
    }
};

class Solution_Net {
public:
     int ladderLength(string start, string end, unordered_set<string> &dict) 
     {
         queue<pair<string, int> > queue;
         queue.push(make_pair(start, 1));
         dict.insert(end);
         while (!queue.empty())
         {
            pair<string, int> cur = queue.front();   
            queue.pop();
            if (cur.first == end)
            {
                return cur.second;
            }

            for (string word : getNeighbors(cur.first, dict))
            {
                queue.push(make_pair(word, cur.second+1));
            }
         }

         return 0;
     }

     vector<string> getNeighbors(string const & word, unordered_set<string> &dict)
     {
        vector<string> res;
        for (size_t i = 0; i < word.size(); i++)
        {
            string copy(word);
            for (char c = 'a'; c <= 'z'; c++)
            {
                copy[i] = c;
                if (dict.find(copy) != dict.end())
                {
                    res.push_back(copy);
                    dict.erase(copy);
                }
            }
        }
        return res;
     }
};
